# 求和
def sum(n):
    if n <= 1:
        return n
    return n + sum(n-1)

# 计算斐波那契数列第 N 项
# O(2^n): 借助于调用过程
# O(n) 空间复杂度
def f1(n):
    if n <= 1:
        return n
    return f1(n - 1) + f1(n - 2)

# O(n) 时间复杂度
# O(1) 空间复杂度
def f2(n):
    if n <= 1:
        return n
    first = 0
    second = 1
    for i in range(n - 1):
        sum_val = first + second
        first = second
        second = sum_val
    return second

# 程序入口点
if __name__ == "__main__":
    print(sum(4))  # 输出结果：10
    print(f1(10))  # 输出 55
    print(f2(10))  # 输出 55